package com.cat.dataStructure;

import java.util.HashSet;
import java.util.Set;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/distinct-echo-substrings/description/
 * @create 2025/9/27 19:33
 * @since JDK17
 */

public class Solution85 {
    long[] p, h;
    long get(int l, int r) {
        long ans = h[r];
        return ans - (l == 0 ? 0 : h[l - 1] * p[r - l + 1]);
    }
    public int distinctEchoSubstrings(String text) {
        Set<Long> set = new HashSet<>();
        char[] arr = text.toCharArray();
        int ans = 0, n = text.length(), base = 499, m = n / 2;
        p = new long[n];
        h = new long[n];
        p[0] = 1;
        h[0] = arr[0] - 'a' + 1;
        for (int i = 1; i < n; i++) {
            p[i] = p[i - 1] * base;
            h[i] = h[i - 1] * base + arr[i] - 'a' + 1;
        }
        for (int len = 1; len <= m; len++) {
            for (int r = len - 1; r < n - len; r++) {
                long t1 = get(r + 1, r + len), t2 = get(r - len + 1, r);
                if (t2 == t1 && !set.contains(t1)) {
                    set.add(get(r + 1, r + len));
                    ans++;
                }
            }
        }

        return ans;
    }
}
